package org.bear.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Solution {

    HashMap<Character, Integer> map = new HashMap<>();

//    给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
//    换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
    public boolean checkInclusion(String s1, String s2) {
        if (s2.length()<s1.length()){
            return false;
        }
        for(int i=0;i<s1.length();i++){
            add(s1.charAt(i));
            sub(s2.charAt(i));
        }
        if (map.isEmpty()){
            return true;
        }

        for (int i = s1.length(); i < s2.length(); i++) {
            sub(s2.charAt(i));
            add(s2.charAt(i-s1.length()));
            if (map.isEmpty()){
                return true;
            }
        }
        return false;
    }


    private void add(char c){
        Integer v = map.get(c);
        if (v==null){
            map.put(c, 1);
        } else if (v==-1) {
            map.remove(c);
        } else {
            map.put(c, v+1);
        }
    }


    private void sub(char c){
        Integer v = map.get(c);
        if (v==null){
            map.put(c, -1);
        }else if (v==1){
            map.remove(c);
        }else {
            map.put(c, v-1);
        }
    }

    private boolean equal(int[] a, int[] b){
        for (int i = 0; i < a.length; i++) {
            if(a[i]!=b[i]){
                return false;
            }
        }
        return true;
    }


    //    给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
    //    变位词 指字母相同，但排列不同的字符串。
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<>();
        }
        int[] arr = new int[26];
        int[] flowArr = new int[26];
        List<Integer> res = new ArrayList<Integer>();
        for(int i=0;i<p.length();i++){
            arr[p.charAt(i)-'a']++;
            flowArr[s.charAt(i)-'a']++;
        }
        if(equal(arr, flowArr)){
            res.add(0);
        }
        for (int i = p.length(); i < s.length(); i++) {
            flowArr[s.charAt(i)-'a']++;
            flowArr[s.charAt(i-p.length())-'a']--;
            if(equal(arr, flowArr)){
                res.add(i-p.length()+1);
            }
        }
        return res;
    }


    //    给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
    public int lengthOfLongestSubstring(String s) {
        int[] arr = new int[128];
        for(int i=0;i<128;i++){
            arr[i] = -1;
        }
        int res = 0;
        for(int i=0,j=0;j<s.length();j++){
            int lastIndex = arr[s.charAt(j)];
            if (lastIndex>-1){
                i=Math.max(lastIndex+1, i);
            }
            arr[s.charAt(j)] = j;
            res = Math.max(res, j-i+1);
        }
        return res;
    }




    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abba"));
    }
}
